/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 冒泡;

/**
 * @Description 冒泡排序
 * 经典的排序算法
 * 基本思想是：
 * 通过对待排序序列从前向后（从下标较小的元素开始）,
 * 依次比较相邻元素的值，若发现逆序则交换，
 * 使值较大的元素逐渐从前移向后部，
 * 就像水底下的气泡一样逐渐向上冒。
 * <p>
 * 进行了优化
 * 因为排序的过程中，各元素不断接近自己的位置，如果一次内循环比较下
 * 来没有进行过交换，就说明序列有序。
 * @Author 俊昭
 * @Date 2022/4/30
 */
public class Bubble {
    /**
     * @param arr 需要排序的数组
     * @return 排好序的数组
     * @description 升序冒泡排序
     */
    public static int[] sort(int[] arr) {
        int len = arr.length;
        boolean flag = false;
        for (int i = 0; i < len - 1; i++) {

            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    flag = true;// 只要被调用就说明没排好序
                }
            }
//            for (int i1 : arr) {
//                System.out.print(i1+"\t");
//            }
//            System.out.println();
            if (! flag) {
                // 内循环内一次不符合顺序的也没有说明排好序了 退出
                break;
            } else {
                flag = false;
            }
        }
        return arr;
    }

    /**
     * @param arr 需要排序的数组
     * @return 排好序的数组
     * @description 降序冒泡排序
     */
    public static int[] sortReversed(int[] arr) {
        int len = arr.length;
        boolean flag = false;
        int temp;
        for (int i = 0; i < len - 1; i++) {

            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    flag = true;// 只要被调用就说明没排好序
                }
            }
            if (! flag) {
                // 内循环内一次不符合顺序的也没有说明排好序了 退出
                break;
            } else {
                flag = false;
            }
        }
        return arr;
    }
}
